|
In mathematics, a discrete logarithm is an integer ''k'' solving the equation , where ''b'' and ''g'' are elements of a finite group. Discrete logarithms are thus the finite-group-theoretic analogue of ordinary logarithms, which solve the same equation for real numbers ''b'' and ''g'', where ''b'' is the base of the logarithm and ''g'' is the value whose logarithm is being taken. No efficient general method for computing discrete logarithms on conventional computers is known. Several important algorithms in public-key cryptography base their security on the assumption that the discrete logarithm problem over carefully chosen groups has no efficient solution. == Example == Discrete logarithms are perhaps simplest to understand in the group (Z''p'')×. This is the group of multiplication modulo the prime ''p''. Its elements are congruence classes modulo ''p'', and the group product of two elements may be obtained by ordinary integer multiplication of the elements followed by reduction modulo ''p''. The ''k''th power of one of the numbers in this group may be computed by finding its ''k''th power as an integer and then finding the remainder after division by ''p''. When the numbers involved are large, it is more efficient to reduce modulo ''p'' multiple times during the computation. Regardless of the specific algorithm used, this operation is called modular exponentiation. For example, consider (Z17)×. To compute 34 in this group, compute 34 = 81, and then divide 81 by 17, obtaining a remainder of 13. Thus 34 = 13 in the group (Z17)×. The discrete logarithm is just the inverse operation. For example, consider the equation 3''k'' ≡ 13 (mod 17) for ''k''. From the example above, one solution is ''k'' = 4, but it is not the only solution. Since 316 ≡ 1 (mod 17)—as follows from Fermat's little theorem—it also follows that if ''n'' is an integer then 34+16''n'' ≡ 34 × (316)''n'' ≡ 13 × 1''n'' ≡ 13 (mod 17). Hence the equation has infinitely many solutions of the form 4 + 16''n''. Moreover, since 16 is the smallest positive integer ''m'' satisfying 3''m'' ≡ 1 (mod 17), i.e. 16 is the order of 3 in (Z17)×, these are the only solutions. Equivalently, the set of all possible solutions can be expressed by the constraint that ''k'' ≡ 4 (mod 16). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Discrete logarithm」の詳細全文を読む スポンサード リンク
|